/**
 * //给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * //
 * // 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * //
 * //
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：nums = [1,2,2]
 * //输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：nums = [0]
 * //输出：[[],[0]]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 10
 * // -10 <= nums[i] <= 10
 * //
 * //
 * //
 * // Related Topics 位运算 数组 回溯 👍 797 👎 0
 */

package com.xixi.basicAlgroithms.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ID00090SubsetsIi {
    public static void main(String[] args) {
        Solution solution = new ID00090SubsetsIi().new Solution();
        System.out.println(solution.subsetsWithDup(new int[]{1,2,2}));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public List<List<Integer>> result = new ArrayList<>();

        public List<List<Integer>> subsetsWithDup(int[] nums) {

            //先排序，让两个相等的元素挨在一起
            Arrays.sort(nums);
            //用来记录当前层，上条数据是否在path中
            boolean[] used = new boolean[nums.length];
            List<Integer> path = new ArrayList<>();

            //开始递归决策
            backTracking(nums, nums.length, 0, used, path);

            return result;
        }


        public void backTracking(int[] nums, int nLength, int index, boolean[] used, List<Integer> path) {
            if (index == nLength) { //遍历到最后拍照
                result.add(new ArrayList<>(path));
                return;
            }
            //每次决策都有放不放这个节点

            if(index == 0){ //第一层进来直接就放
                path.add(nums[index]);
                used[index] = true;
                backTracking(nums, nLength, index + 1, used, path);//放
                path.remove(path.size() - 1);
            }else{//从数组第二位开始需要判断
                if (nums[index] == nums[index - 1] //前一个数字是否和它相等
                        && !used[index - 1]) { //如果相等，按照递归顺序，used[index-1] == false的时候说明包含前面那个相等数字的子集已经出现在结果集里面了，所以当前数字就不要再放了，肯定会重复的。
                    //再包含这个节点的子集与上个相同了
                }else{ //如果和上个数字不相等，或者前一个数字放在path里了，说明还需要递归包含当前数字的子树
                    path.add(nums[index]);
                    used[index] = true;
                    backTracking(nums, nLength, index + 1, used, path);//放
                    path.remove(path.size() - 1);
                }
            }



            used[index] = false;
            backTracking(nums, nLength, index + 1, used, path);//不放








        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}